#pragma once
#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<assert.h>
using namespace std;


class Maze
{
public:
	Maze()
	{
		cin >> _rows >> _cols;
		_pool = (int**)malloc(sizeof(int*) * _rows);
		assert(_pool);
		for (int i = 0; i < _rows; i++)
		{
			_pool[i] = (int*)malloc(sizeof(int) * _cols);
			assert(_pool[i]);
		}

		for (int i = 0; i < _rows; i++)
		{
			for (int j = 0; j < _cols; j++)
			{
				cin >> _pool[i][j];
			}
		}
		_node._x = _node._y = 0;
	}

	void Print();

	bool GetPassage(int x = 0, int y = 0);
	void Print_Passage()
	{
		Stack newstack, oldstack = _stack;
		while (!oldstack.IsEmpity())
		{
			newstack.Push(oldstack.Top());
			oldstack.Pop();
		}
		while (!newstack.IsEmpity())
		{
			printf("(%d,%d)\n", newstack.Top()._y, newstack.Top()._x);
			newstack.Pop();
		}
	}

	~Maze()
	{
		for (int i = 0; i < _rows; i++)
		{
			free(_pool[i]);
		}
		free(_pool);
	}
private:
	bool IsNodeTure(int x = 0, int y = 0);

	class Node
	{
	public:
		Node(int x = 0, int y = 0)
		{
			_x = x;
			_y = y;
		}

		int _x;
		int _y;
	};

	typedef Node TypeData;
	class Stack
	{
	public:
		Stack(int size = 4)
			:_capacity(size)
			, _size(-1)
		{
			_a = (TypeData*)malloc(sizeof(TypeData) * size);
			assert(_a);
		}

		TypeData Top()
		{
			assert(_size >= 0);
			return _a[_size];
		}

		void Pop()
		{
			assert(_size >= 0);
			_size--;
		}

		bool IsEmpity()
		{
			if (_size == -1)
				return 1;
			else
				return 0;
		}

		void Push(TypeData x);

		

		Stack(Stack& s)
		{
			int size = s.GetSize();
			_a = (TypeData*)malloc(sizeof(TypeData) * s.GetCapacity());
			assert(_a);
			_size = size;
			_capacity = s.GetCapacity();
			for (int i = 0; i <= size; i++)
			{
				_a[i]._x = s._a[i]._x;
				_a[i]._y = s._a[i]._y;
			}
		}

		~Stack()
		{
			free(_a);
		}

	private:
		int GetSize()
		{
			return _size;
		}

		int GetCapacity()
		{
			return _capacity;
		}

		TypeData* _a;
		int _size;
		int _capacity;
	};

	int _rows;
	int _cols;
	Node _node;
	int** _pool;
	Stack _stack;
};


//5 5
//1 0 1 0 1
//0 0 0 0 0
//1 1 0 1 1
//0 0 0 1 1
//1 0 0 0 0